import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-07-18
 * Time: 22:36
 */
public class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        int result = 0;
        int row = maze.length;
        int col = maze[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(entrance);
        int[][] next = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!queue.isEmpty()) {
            int size = queue.size();
            // 遍历一层
            for (int i = 0; i < size; i++) {
                int[] position = queue.poll();
                int x = position[0];
                int y = position[1];
                // 找到出口
                if (!(x == entrance[0] && y == entrance[1]) && maze[x][y] == '.'
                        && (x == 0 || y == 0 || x == (row - 1) || y == (col-1))) {
                    return result;
                }
                // 先标记为 已经遍历过
                maze[x][y] = '+';
                // 上下左右
                for (int j = 0; j < 4; j++) {
                    int nextX = x + next[j][0];
                    int nextY = y + next[j][1];
                    if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col
                            || maze[nextX][nextY] == '+') {
                        // 越界了 或者遇到墙了
                        continue;
                    }
                    // 正常情况
                    queue.add(new int[]{nextX, nextY});
                }
            }
            result++;
        }
        return -1;
    }
}